#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#include "boolean.h"

typedef int Matrix[9][9];

boolean isRowValid(Matrix pMatrix, int pNumber, int pRow)
{
    int tCol;
    for (tCol=0;tCol<9;tCol++) {
        if (pMatrix[pRow][tCol] == pNumber) {
            return false;
        }
    } //tCol == 9;
    return true;
}

boolean isColValid(Matrix pMatrix, int pNumber, int pCol)
{
    int tRow;
    for (tRow=0;tRow<9;tRow++) {
        if (pMatrix[tRow][pCol] == pNumber) {
            return false;
        }
    } //tRow == 9;
    return true;
}

boolean isSquareValid(Matrix pMatrix, int pNumber, int pRow, int pCol)
{
    //ada 9 persegi
    int tRow, tCol;
    if ((pRow>=0) && (pRow<=2)) {
        //periksa 3 kolom
        if ((pCol>=0) && (pCol<=2)) {
            //printf("top-left square \n");
            for (tRow=0;tRow<=2;tRow++) {
                for (tCol=0;tCol<=2;tCol++) {
                    if (pMatrix[tRow][tCol] == pNumber) {
                        return false;
                    }
                }
            }
        } else
        if ((pCol>=3) && (pCol<=5)) {
            //printf("top-mid square \n");
            for (tRow=0;tRow<=2;tRow++) {
                for (tCol=3;tCol<=5;tCol++) {
                    if (pMatrix[tRow][tCol] == pNumber) {
                        return false;
                    }
                }
            }
        } else
        if ((pCol>=6) && (pCol<=8)) {
            //printf("top-right square \n");
            for (tRow=0;tRow<=2;tRow++) {
                for (tCol=6;tCol<=8;tCol++) {
                    if (pMatrix[tRow][tCol] == pNumber) {
                        return false;
                    }
                }
            }
        }
    } else //bagian tengah
    if ((pRow>=3) && (pRow<=5)) {
        //periksa 3 kolom
        if ((pCol>=0) && (pCol<=2)) {
            //printf("mid-left square \n");
            for (tRow=3;tRow<=5;tRow++) {
                for (tCol=0;tCol<=2;tCol++) {
                    if (pMatrix[tRow][tCol] == pNumber) {
                        return false;
                    }
                }
            }
        } else
        if ((pCol>=3) && (pCol<=5)) {
            //printf("mid-mid square \n");
            for (tRow=3;tRow<=5;tRow++) {
                for (tCol=3;tCol<=5;tCol++) {
                    if (pMatrix[tRow][tCol] == pNumber) {
                        return false;
                    }
                }
            }
        } else
        if ((pCol>=6) && (pCol<=8)) {
            //printf("mid-right square \n");
            for (tRow=3;tRow<=5;tRow++) {
                for (tCol=6;tCol<=8;tCol++) {
                    if (pMatrix[tRow][tCol] == pNumber) {
                        return false;
                    }
                }
            }
        }
    } else //bagian bawah
    if ((pRow>=6) && (pRow<=8)) {
        //periksa 3 kolom
        if ((pCol>=0) && (pCol<=2)) {
            //printf("bottom-left square \n");
            for (tRow=6;tRow<=8;tRow++) {
                for (tCol=0;tCol<=2;tCol++) {
                    if (pMatrix[tRow][tCol] == pNumber) {
                        return false;
                    }
                }
            }
        } else
        if ((pCol>=3) && (pCol<=5)) {
            //printf("bottom-mid square \n");
            for (tRow=6;tRow<=8;tRow++) {
                for (tCol=3;tCol<=5;tCol++) {
                    if (pMatrix[tRow][tCol] == pNumber) {
                        return false;
                    }
                }
            }
        } else
        if ((pCol>=6) && (pCol<=8)) {
            //printf("bottom-right square \n");
            for (tRow=6;tRow<=8;tRow++) {
                for (tCol=6;tCol<=8;tCol++) {
                    if (pMatrix[tRow][tCol] == pNumber) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

boolean isValid(Matrix pMatrix, int pNumber, int pRow, int pCol)
{
    return (((isRowValid(pMatrix, pNumber, pRow)) && (isColValid(pMatrix, pNumber, pCol))) && (isSquareValid(pMatrix, pNumber, pRow, pCol)));
}



void openFile (char pFileName[32], Matrix pMatrix)
{
    int tRow,tCol;
    char tLine[32];
    char *pch;
    FILE *tFile;
    tFile = fopen(pFileName,"r");
    for (tRow=0;tRow<=8;tRow++) {
        fgets(tLine, 32, tFile);
        pch = strtok (tLine," ");
        for (tCol=0;tCol<=8;tCol++) {
            pMatrix[tRow][tCol] = atoi(pch);
            pch = strtok (NULL, " ");
        }
    }
}

void copyMatrix (Matrix pInMatrix, Matrix pOutMatrix)
{
    int curRow, curCol;
    for(curRow=0;curRow<=8;curRow++) {
        for (curCol=0;curCol<=8;curCol++) {
            pOutMatrix[curRow][curCol] = pInMatrix[curRow][curCol];
        }
    }

}

void printMatrix (Matrix pMatrix)
{
    int curRow, curCol;
    printf("\n-----------------------\n");
    for(curRow=0;curRow<=2;curRow++) {
        for (curCol=0;curCol<=2;curCol++) {
            printf("%d ",pMatrix[curRow][curCol]);
        } printf("| ");
        for (curCol=3;curCol<=5;curCol++) {
            printf("%d ",pMatrix[curRow][curCol]);
        } printf("| ");
        for (curCol=6;curCol<=8;curCol++) {
            printf("%d ",pMatrix[curRow][curCol]);
        } printf("| ");
        printf("\n");
    }
    printf("-----------------------\n");

    for(curRow=3;curRow<=5;curRow++) {
        for (curCol=0;curCol<=2;curCol++) {
            printf("%d ",pMatrix[curRow][curCol]);
        } printf("| ");
        for (curCol=3;curCol<=5;curCol++) {
            printf("%d ",pMatrix[curRow][curCol]);
        } printf("| ");
        for (curCol=6;curCol<=8;curCol++) {
            printf("%d ",pMatrix[curRow][curCol]);
        } printf("| ");
        printf("\n");
    }
    printf("-----------------------\n");

    for(curRow=6;curRow<=8;curRow++) {
        for (curCol=0;curCol<=2;curCol++) {
            printf("%d ",pMatrix[curRow][curCol]);
        } printf("| ");
        for (curCol=3;curCol<=5;curCol++) {
            printf("%d ",pMatrix[curRow][curCol]);
        } printf("| ");
        for (curCol=6;curCol<=8;curCol++) {
            printf("%d ",pMatrix[curRow][curCol]);
        } printf("| ");
        printf("\n");
    }
    printf("-----------------------\n");
    printf("\n");
}


int main()
{
    clock_t startTime;
    double diff;
    clock_t endTime;

    startTime = clock();

    Matrix inMatrix, outMatrix;
    int curRow=0,curCol=0,curCell,curNumber;
    int mIteration=0;
    int mBacktrack=0;
    boolean OK;
    boolean backtrack = false;
    char mFileName[32];

    printf("masukan nama file: ");
    scanf("%s",mFileName);
    openFile(mFileName,inMatrix);
    printf("Sudoku Soal");
    printMatrix(inMatrix);
    copyMatrix(inMatrix,outMatrix);

    while (curRow <= 8) {
        while (curCol <= 8) {
            curCell = inMatrix[curRow][curCol];
            if (curCell == 0) {

                if (!backtrack) {
                    curNumber = 1;
                    mIteration++;
                } else {
                    backtrack = false;
                    mBacktrack++;
                }

                OK = false;

                while (!OK) {
                    //printf("%d %d %d\n",curRow,curCol,curNumber);
                    if (isValid(outMatrix,curNumber,curRow,curCol)) {
                        outMatrix[curRow][curCol] = curNumber;
                        OK = true;
                    } else {
                        curNumber++;
                        mIteration++;
                        //kondisi curNumber > 9 -> gak ada yg bener
                        //-> mundur tambah angka soal sebelumnya;
                        if (curNumber > 9) {
                            outMatrix[curRow][curCol] = 0;
                            backtrack = true;
                            do {
                                if (curCol == 0) {
                                    curRow = curRow - 1;
                                    curCol = 8;
                                } else {
                                    curCol = curCol - 1;
                                }
                                curCell = inMatrix[curRow][curCol];
                            } while (curCell != 0);
                            //curCell = 0 -> soal
                            OK = true;
                            curNumber = outMatrix[curRow][curCol];
                            //setelah mundur matrix terisi 9
                            //mundur lagi, kalo gak -> normal -> curNumber++
                            if (curNumber == 9) {
                                outMatrix[curRow][curCol] = 0;
                                backtrack = true;
                                do {
                                    if (curCol == 0) {
                                        curRow = curRow - 1;
                                        curCol = 8;
                                    } else {
                                        curCol = curCol - 1;
                                    }
                                    curCell = inMatrix[curRow][curCol];
                                } while (curCell != 0);
                                OK = true;
                                curNumber = outMatrix[curRow][curCol];
                            } else {
                                curNumber++;
                            }
                        }
                    }
                }
            }
            if (!backtrack) {
                curCol++;
            }
        }
        if (!backtrack) {
            curCol = 0; curRow++;
        }
    }

    printf("Sudoku Jawaban");
    printMatrix(outMatrix);
    printf("\nJumlah iterasi  = %d",mIteration);
    endTime = clock();
    diff = ((double)endTime - (double)startTime) / (double)CLOCKS_PER_SEC;
    printf("\nWaktu eksekusi  = %f\n",diff);

    return 0;
}


